package 单周赛.september;

import java.util.HashSet;
import java.util.Set;

/**
 * @
 * @date 2024/07/21
 */
public class 第407场单周赛 {

    public static void main(String[] args) {

        System.out.println(minChanges(54, 4));

        System.out.println(maxOperations("1001101"));

        // [9,2,6,10,4,8,3,4,2,3]
        //target =
        //[9,5,5,1,7,9,8,7,6,5]
        System.out.println(minimumOperations(
                new int[]{9, 2, 6, 10, 4, 8, 3, 4, 2, 3},
                new int[]{9, 5, 5, 1, 7, 9, 8, 7, 6, 5}
        ));
    }

    public static int minChanges(int n, int k) {

        int min = 0;
        String a = Integer.toBinaryString(n);
        String b = Integer.toBinaryString(k);

        if (b.length() > a.length()) {
            return -1;
        }

        a = new StringBuilder(a).reverse().toString();
        b = new StringBuilder(b).reverse().toString();
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) == '0' && i < b.length() && b.charAt(i) == '1') {
                return -1;
            }
            if (a.charAt(i) == '1' && (i >= b.length() || b.charAt(i) == '0')) {
                min++;
            }
        }

        return min;
    }

    public boolean doesAliceWin(String s) {

        Set<Character> set = new HashSet<>();
        for (char c : "aeiou".toCharArray()) {
            set.add(c);
        }

        int cnt = 0;
        for (char c : s.toCharArray()) {
            if (set.contains(c)) {
                cnt++;
            }
        }
        if (cnt == 0) {
            return false;
        }
        return true;
    }

    public static int maxOperations(String s) {
        int ans = 0;

        int zeroCnt = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                while (i >= 0 && s.charAt(i) == '0') {
                    i--;
                }
                zeroCnt++;
                continue;
            }
            ans += zeroCnt;
        }

        return ans;
    }

    /**
     * 相减之后变成一个新的数组，子数组不可能同时包含正数和负数
     * 找到连续是正数或者负数的子数组，求出数组中相邻两元素的差值，保留大于 0 的部分，累加即为答案。
     */
    public static long minimumOperations(int[] nums, int[] target) {
        long ans = 0;
        int left = 0;

        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] - target[i];
        }

        while (left < nums.length) {
            if (nums[left] == 0) {
                left++;
                continue;
            }

            ans += Math.abs(nums[left]);
            int right = left + 1;
            while (
                    right < nums.length && (nums[left] < 0 && nums[right] < 0 ||
                            nums[left] > 0 && nums[right] > 0)) {
                int diff = Math.abs(nums[right]) - Math.abs(nums[right - 1]);
                if (diff > 0) {
                    ans += diff;
                }
                right++;
            }

            left = right;
        }

        return ans;
    }
}
